package com.dyz.leetcode;

import java.util.Stack;

public class DailyTemperatures739 {
    /** 单调栈--> 单调递减栈
     * 分析题意：这里我们用到了栈的结构，并且栈中的温度数值的下标
     * 结果数组我们定义为dist[n], 大小n就是温度数组的长度
     * 遍历温度数组，当前遍历下标（记作，curindex）对应温度大于栈顶元素对应下标温度时，说明栈顶元素作为下标对应温度
     * 的下一个比它大的温度数就是当前元素。满足条件，就让栈顶元素（记， preIndex）弹出栈，其就是对应要存储的位置的下
     * 标，然后对应下标的结果数组dist[preIndex]=curIndex-preIndex;这样就巧妙的利用了下标差来当作下一次升温的天数。
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int n = temperatures.length;
        int[] dist = new int[n];
        for(int curIndex=0; curIndex<n; curIndex++){
            while (!stack.isEmpty() && temperatures[curIndex]> temperatures[stack.peek()]){
                int preIndex = stack.pop();
                dist[preIndex] = curIndex - preIndex;
            }
            stack.add(curIndex);
        }
        return dist;
    }
}
